package com.cat.graphTheory;

import java.util.Arrays;

/**
 *   @description https://leetcode.cn/problems/minimize-malware-spread/description/
 *   @author 曲大人的喵
 *   @create 2025/9/19 15:42
 *   @since JDK17
 */

public class Solution11 {
    int n, cnt, size;
    int[][] g;
    boolean[] isInitial, vis;

    void dfs(int cur) {
        vis[cur] = true;
        size++;
        cnt += isInitial[cur] ? 1 : 0; // 被感染的结点

        for (int i = 0; i < n; i++) {
            if (g[cur][i] != 0 && !vis[i]) {
                dfs(i);
            }
        }
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        n = graph.length;
        g = graph;
        vis = new boolean[n];
        isInitial = new boolean[n];
        int ans = -1, maxSize = Integer.MIN_VALUE;
        for (int x : initial) {
            isInitial[x] = true;
        }
        Arrays.sort(initial);
        for (int x : initial) {
            if (vis[x]) { // 该联通块至少包含了两个被感染结点
                continue;
            }
            cnt = size = 0;
            dfs(x);
            if (cnt == 1 && maxSize < size) {
                ans = x;
                maxSize = size;
            }
        }
        return ans < 0 ? initial[0] : ans;
    }
}
